package com.example.code.class02;

/**
 * @Date 2022/7/16
 * @Created by Jonathan
 */
public class Code04_Drive {

    public static void main(String[] args) {
//        maxMoney()

    }


    private static int maxMoney(int[][] income) {
        if (income == null || income.length < 2 || (income.length & 1) != 0) {
            return 0;
        }
        int N = income.length;
        int M = N >> 1; // M = N/2;

        return process(income, 0, M);
    }

    /**
     * index...所有司机往AB分配
     * A区域还有rest个名额
     * 返回把index...，司机，分配完，并且最终A和B同样多的情况下，整体收入最大是多少?
     */
    private static int process(int[][] income, int index, int rest) {
        if (income.length == index) {
            return 0;
        }
        // 这个边界！！！
        // 还剩下的司机正好和rest(A区域剩下的名额)相等
        if (income.length - index == rest) {
            return income[index][0] + process(income, index + 1, rest - 1);
        }

        // A区域已经没有名额 只能全部去B
        if (rest == 0) {
            return income[index][1] += process(income, index + 1, rest);
        }

        // index 去A 那么A区域的名额就是rest-1
        int goA = income[index][0] + process(income, index + 1, rest - 1);
        // index 去B 那么A区域的名额就是rest
        int goB = income[index][1] + process(income, index + 1, rest);
        return Math.max(goA, goB);
    }
}
